package day03;

import java.util.Scanner;

public class FindGcdAndLcm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r;
        int a = sc.nextInt();
        int b = sc.nextInt();
////        for (; a % b != 0; ) {//1.通过辗转相除法求两个数的最大公倍数
////            r = a % b;
////            a = b;
////            b = r;
////        }

//        for( r=1;;){//2.通过更相减损术求两个数的最大公倍数
//            if(a%2==0&&b%2==0){//1.判断两个数是否同为偶数，是则同时除以2再用r的值存这个公倍数
//                a/=2;
//                b/=2;
//                r*=2;
//            }
//            else {//2.为奇数则开始辗转相减,（大数减小数的差再去减上一个式子里的减数一直减到差等于减数时停止）
//               if(a>b){//始终保持大数减小数
//                   a-=b;
//                   if(a==b){
//                       break;
//                   }
//                   b=a+b;
//                   a=b-a;
//                   b-=a;
//               }
//                else {
//                    b-=a;
//                   if(a==b){
//                       break;
//                   }
//                    a=b+a;
//                    b=a-b;
//                    a-=b;
//                }
//            }
//
//        }
//
//        System.out.println("两数的GCD为"+a*r);//最小公倍数等于r所存的公倍数乘以第二步的所得到的差

        int Gcd = gcd(a, b);
        long Lcm = lcm(a, b);
        System.out.println("最大公因子:" + Gcd);
        System.out.println("最小公倍数:" + Lcm);
    }

    //    private static int gcd(int a, int b) {// 辗转相除+递归
//        if ( b==0){
//            return a;
//        }
//        else {
//            return gcd(b,a%b);
//        }
//
//    }
//    private static int lcm(int a, int b){// a*b=gcd*lcm > lcm = a*b/gcd
//        int n=gcd(a,b);
//            return a / n * b;
//    }
    private static int gcd(int a, int b) {
        int min = a > b ? b : a;
        for (; min >= 1; min--) {
            if (a % min == 0 && b % min == 0) {//穷举法求出最小公倍数
                    return min;
            }
        }
        return 0;
    }

    private static int lcm(int a, int b) {
        int max = a > b ? a : b;
        for (long i=max;; i+=max ) {
            if (i % a == 0 && i % b == 0) {//穷举法求最小公倍数
                return (int) i;
//                int n=gcd(a,b);
//                return a / n * b; //∵a*b=gcd*lcm ∴lcm = a*b/gcd 公式推导

            }

        }

    }

}
